#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/8/24 16:46
# @Author  : Yuyun
# @File    : 计数排序.py
# @IDE     : PyCharm


#其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
# 作为一种线性时间复杂度的排序，它要求输入的数据必须是有确定范围的整数
"""
找出待排序的数组中最大和最小的元素。
统计数组中每个值为i的元素出现的次数，存入数组C的第i项。
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）。
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
"""


def counting_sort(arr):
    # 找出数组中的最大值和最小值
    max_val = max(arr)
    min_val = min(arr)

    # 计算数组的长度
    range_of_elements = max_val - min_val + 1

    # 初始化计数数组，长度为范围+1，并将所有元素初始化为0
    count_arr = [0] * range_of_elements

    # 计算每个元素的出现次数
    for num in arr:
        count_arr[num - min_val] += 1

        # 更改count_arr，使得每个位置包含的是小于等于该值的元素个数
    for i in range(1, len(count_arr)):
        count_arr[i] += count_arr[i - 1]

        # 初始化输出数组
    output_arr = [0] * len(arr)

    # 构建输出数组
    # 从后向前遍历输入数组，保证稳定性（相等元素的相对顺序不变）
    for j in range(len(arr) - 1, -1, -1):
        output_arr[count_arr[arr[j] - min_val] - 1] = arr[j]
        count_arr[arr[j] - min_val] -= 1

        # 返回排序后的数组
    return output_arr


# 示例
arr = [4, -2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("Sorted array is:", sorted_arr)